package leetcode.code1028;

import leetcode.IDebug;
import leetcode.helper.tree.TreeNode;

public class Solution implements IDebug {

	public TreeNode recoverFromPreorder(String traversal) {
		char[] cs = traversal.toCharArray();
		int[] ss = new int[cs.length];
		int pss = 0;
		int pcs = 0;
		while (pcs < cs.length) {
			if (cs[pcs] == '-') {
				ss[pss++] = -1;
				pcs++;
			} else {
				int num = cs[pcs] - '0';
				pcs++;
				while (pcs < cs.length && cs[pcs] != '-') {
					num = num * 10 + cs[pcs] - '0';
					pcs++;
				}
				ss[pss++] = num;
			}
		}
//		H.printObject(ss);
		return this.recoverFromPreorder(ss, 0, 0, pss - 1);
	}

	private TreeNode recoverFromPreorder(int[] cs, int h, int l, int r) {
		int val = cs[l];
		TreeNode ans = new TreeNode(val);
		if (l != r) {
//			"1-401--349---90--88"
			int nexth = h + 1;
			int count = 0;
			int last = l + nexth + 1;
			int lr = r;
			int rl = -1;
			for (int i = last; i <= r; i++) {
				if (cs[i] == -1) {
					count++;
				} else {
					if (count == nexth) {
						lr = i - nexth - 1;
						rl = i;
						break;
					} else {
						count = 0;
						last = i;
					}
				}
			}
			ans.left = this.recoverFromPreorder(cs, nexth, l + nexth + 1, lr);
			if (rl != -1) {
				ans.right = this.recoverFromPreorder(cs, nexth, rl, r);
			}
		}
		return ans;
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.recoverFromPreorder("1-401--349---90--88");
//		so.recoverFromPreorder("1-2--3--4-5--6--7");
	}

}
